import java.util.Arrays;

/*
 * @lc app=leetcode.cn id=53 lang=java
 *
 * [53] 最大子序和
 */

// @lc code=start
class Solution {
    public int maxSubArray(int[] nums) {

        int[] dp = new int[nums.length + 1];

        for (int i = 1; i < dp.length; i++) {
            dp[i] = Math.max(nums[i-1], dp[i-1] + nums[i-1]);
        }

        Arrays.sort(dp, 1, dp.length);
        return dp[dp.length - 1]; 
    }
}
// @lc code=end

